#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<string>
#include<stack>

using namespace std;

//bool isnumber(string str)
//{
//    char c = str[str.size()-1];
//    if (c >= '0' && c <= '9')
//        return true;
//    return false;
//}
//
//int Ret(string str, int left, int right)
//{
//    char c = str[0];
//    switch (c)
//    {
//    case '+':
//        return left + right;
//    case '-':
//        return left - right;
//    case '*':
//        return left * right;
//    case '/':
//        return left / right;
//    }
//    return 0;
//}
//
//int evalRPN(const vector<string>& tokens) {
//    stack<int> st;
//    int i = 0;
//    while (i < tokens.size())
//    {
//        if (isnumber(tokens[i]))
//        {
//            st.push(stoi(tokens[i]));
//        }
//        else
//        {
//            int right = st.top();
//            st.pop();
//            int left = st.top();
//            st.pop();
//            int n = Ret(tokens[i], left, right);
//            st.push(n);
//        }
//        i++;
//    }
//    return st.top();
//}
//
//int main()
//{
//    //cout << evalRPN({ "1","2","+" }) << endl;
//    cout << evalRPN({ "10","6","9","3","+","-11","*","/","*","17","+","5","+" }) << endl;
//    return 0;
//}



void MergeSort(vector<int>& v,int left,int right)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	MergeSort(v, left, mid);
	MergeSort(v, mid + 1, right);

	vector<int> tmp(v);
	int l1 = left;
	int r1 = mid;
	int l2 = mid + 1;
	int r2 = right;
	int i = l1;

	while (l1<=r1 || l2<=r2)
	{
		if (l1 > r1)
			tmp[i++] = v[l2++];
		else if (l2 > r2)
			tmp[i++] = v[l1++];
		else
		{
			if (v[l1] <= v[l2])
				tmp[i++] = v[l1++];
			else
				tmp[i++] = v[l2++];
		}
	}
	v = tmp;
}

int main()
{
	vector<int> v = { 10,6,7,1,3,9,4,2 };
	MergeSort(v, 0, v.size() - 1);

	return 0;
}






























